package ltd.dujiabao.alog.dynamicprograming;

import java.util.Arrays;

/**
 * @author : DuJiabao
 * @Project : sword-finger-offer
 * @Time : 2021/4/13 23:18
 * @Desc : 墙
 */
public class Practice1 {
  public static int practice0(boolean[][] graph) {
    int height = graph.length;
    int width = graph[0].length;
    int[][] status = new int[height][width];
    for (int i = 0; i < height; i++) {
      for (int j = 0; j < width; j++) {
        status[i][j] = 0;
        if (!graph[i][j])
          continue;
        if (i == 0 && j == 0)
          status[i][j] = 1;
        if (i != 0)
          status[i][j] += status[i - 1][j];
        if (j != 0)
          status[i][j] += status[i][j - 1];
      }
    }
    for (int[] ints : status) {
      for (int item : ints) {
        System.out.print(item + " ");
      }
      System.out.println();
    }
    return status[height - 1][width - 1];
  }

  public static int practice(boolean[][] graph) {
    int height = graph.length;
    int width = graph[0].length;
    int[][] status = new int[height][width];
    // 出发点
    status[0][0] = 1;
    // 第一行
    for (int i = 1; i < width; i++) {
      if (graph[0][i]) {
        status[0][i] = status[0][i - 1];
      } else {
        status[0][i] = 0;
      }
    }
    // 第一列
    for (int i = 1; i < height; i++) {
      if (graph[i][0]) {
        status[i][0] = status[i - 1][0];
      } else {
        status[i][0] = 0;
      }
    }
    // 第二列和第二行开始
    for (int i = 1; i < height; i++) {
      for (int j = 1; j < width; j++) {
        if (graph[i][j]) {
          status[i][j] = status[i - 1][j] + status[i][j - 1];
        } else {
          status[i][j] = 0;
        }
      }
    }
    return status[height - 1][width - 1];
  }


  public static void main(String[] args) {
    boolean[][] graph = new boolean[8][8];
    for (int i = 0; i < graph.length; i++) {
      for (int j = 0; j < graph[0].length; j++) {
        graph[i][j] = true;
      }
    }
    graph[1][2] = false;
    graph[1][6] = false;
    graph[2][4] = false;
    graph[3][0] = false;
    graph[3][2] = false;
    graph[3][5] = false;
    graph[4][2] = false;
    graph[5][3] = false;
    graph[5][4] = false;
    graph[5][6] = false;
    graph[6][1] = false;
    graph[6][5] = false;
    int res = practice(graph);
    System.out.println(res);
  }
}
